#include "insertionsort.h"

using namespace std;



// merge subfunction, assuming s1~e1~s2~e2 memory location are continuous
// s1~e1, s2~e2 are sorted already
static int memnum=0;
struct h{
	int *p;
	h(int n_):p(new int[n_]){memnum++;}
	~h(){delete [] p;}
};

void m(int a[], int s1, int e1, int s2, int e2){
	if (a[e1]<a[s2]){
		//return;
	}else{
		h pp(e2-s2+1);
		memcpy(pp.p,a+s2,(e2-s2+1)*sizeof(int));//sizeof int
		int k=e2;
		int i=e2-s2;
		int j=e1;
		while(k!=s1){// i>=0 and j>=s1
			//situation 1
			if(i>=0 && j>=s1){
				if (pp.p[i]>a[j]){
					a[k] = pp.p[i];
					i--;
				}else{
					a[k]=a[j];
					j--;
				}
				k--;
			}
			//situation 2
			if (j<s1 &&i>=0){
				memcpy(&a[s1],&pp.p[0],(i+1)*sizeof(int));
				break;
			}
			//situation 3
			if(i<0 && j>=s1){
				break;
			}
		}
	}
}

void m2(int a[], int s1, int e1, int e2,int *p){
	if (a[e1]>a[e1+1]){
		//h pp(e2-e1+1+1);////
		memcpy(p,a+e1+1,(e2-e1+1+1)*sizeof(int));//sizeof int
		int k=e2;
		int i=e2-(e1+1);
		int j=e1;
		while(k!=s1){// i>=0 and j>=s1
			//situation 1
			if(i>=0 && j>=s1){
				if (p[i]>a[j]){
					a[k] = p[i];
					i--;
				}else{
					a[k]=a[j];
					j--;
				}
				k--;
			}
			//situation 2
			if (j<s1 &&i>=0){
				memcpy(&a[s1],&p[0],(i+1)*sizeof(int));
				break;
			}
			//situation 3
			if(i<0 && j>=s1){
				break;
			}
		}
	}
}

void memcpy2(int *dest, int* src, int num){
	while(num-1>=0){
		dest[num-1]=src[num-1];
		num--;
	}
}


void m2inversionpair(int a[], int s1, int e1, int e2,int *p,int &ip){
	if (a[e1]>a[e1+1]){
		//h pp(e2-e1+1+1);////
		//memcpy(p,a+e1+1,(e2-e1+1)*sizeof(int));//sizeof int???????????????????????????????????????
		memcpy2(p,a+e1+1,(e2-e1+1));
		int k=e2;
		int i=e2-(e1+1);
		int j=e1;
		while(k!=s1){// i>=0 and j>=s1
			//situation 1
			if(i>=0 && j>=s1){
				if (p[i]>a[j]){
					a[k] = p[i];
					i--;
				}else{
					a[k]=a[j];
					printf("%d %d\n",p[i],a[j]);
					j--;
					ip++;
				}
				k--;
			}
			//situation 2
			if (j<s1 && i>=0){
				//memcpy(&a[s1],&p[0],(i+1)*sizeof(int));
				memcpy2(a+s1,p,i+1);
				ip += i*(e1-s1+1);//????????????????
				//TODO
				for (int x=0;x<i;x++){
					for (int y=s1;y<=e1;y++){
						printf("%d %d\n",p[x],a[y]);// must use n space, not n/2
					}
				}
				break;
			}
			//situation 3
			if(i<0 && j>=s1){
				break;
			}
		}
	}
}

void mergesort(int a[],int start, int end){
	int size=1;
	int fsize=(end-start);
	int i=0;
	while(size < fsize+1){
		int k=i+2*size-1;
		if (k>end){//logic
			if (i<=end){
				k=end;
				printf("size:%d %d k:%d\n",size,i+size-1,k);
				if(i+size-1<k){
					m(a,i,i+size-1,i+size,k);
				}
			}
			size <<= 1;
			i=0;
		}else{
			m(a,i,i+size-1,i+size,k);// 0011 2233 4455...;  0123 4566...
			i = k+1;
		}
	}
}

void mergesort2(int a[], int start, int end){
	time_t tstart,tend;
	time (&tstart);
	int *p = (int*)calloc((end-start)/2+1,sizeof(int));//new int[(end-start)/2];
	int size=1; // length of left part of two mergers -> rule1: from kstart up to kstart+size-1, data are sorted!!! We use bottom up method.
	if(1){//preprocessing
		int i=start;
		for(;i<end-THRESHOLD;i=i+THRESHOLD){
			insertionsort(a,i,i+THRESHOLD);
		}
		insertionsort(a,i,end+1);
		// printarray(a,100);
		size=THRESHOLD;
	}
	time (&tend);
	double dif = difftime (tend,tstart);
	printf ("step1: %.2lf seconds\n", dif ); //It took you 31.00 seconds to sort.
	time (&tstart);
	int fsize=end-start+1; // the number of elements in array
	int kstart=0;
	while(size < fsize){
		int kend=kstart+(size<<1)-1; // kstart---kstart+size-1,kstart+size---kstart+size+size-1(=kend)
		if (kend>end){ // non-symmetric
			kend = end;
			if (kend-kstart+1 > size){
				m2(a,kstart,kstart+size-1,kend,p);
			}
			size <<= 1;
			kstart=0;
		}else{ // left & right parts have the same number of elements
			m2(a,kstart,kstart+size-1,kend,p);// 0011 2233 4455...;  0123 4566...
			kstart = kend+1;
		}
	}
	time (&tend);
	dif = difftime (tend,tstart);
	printf ("step2: %.2lf seconds\n", dif ); //It took you 31.00 seconds to sort.
	free(p);
}

int mergesort3(int a[], int start, int end){
	if (start==end){
		return 0;
	}
	int fsize=end-start+1; // the number of elements in array
	int inversionpair=0;
	int size=1; // length of left part of two mergers -> rule1: from kstart up to kstart+size-1, data are sorted!!! We use bottom up method.
	int *p = (int*)calloc((fsize>>1)+1,sizeof(int)); // pre-allocate enough memory space
	int kstart=0;
	while(size < fsize){
		int kend=kstart+(size<<1)-1; // kstart---kstart+size-1,kstart+size---kstart+size+size-1(=kend)
		if (kend>end){ // non-symmetric
			kend = end;
			if (kend-kstart+1 <= size){
				;//pass according to rule1
			}else{
				m2inversionpair(a,kstart,kstart+size-1,kend,p,inversionpair);
			}

			size <<= 1;
			kstart=0;
		}else{ // left & right parts have the same number of elements
			m2inversionpair(a,kstart,kstart+size-1,kend,p,inversionpair);// 0011 2233 4455...;  0123 4566...
			kstart = kend+1;
		}
	}
	free(p);
	return inversionpair;
}

void mergesort4(int a[],size_t s){}

void mergesort5(int a[],size_t s){}



void testmerge1(){
	const int N=static_cast<int>(100e6);
	int* a=new int[N];
	for(int i=0;i<N;i++){a[i]=i;}
	random_shuffle(a,a+N);
	time_t start,end;
	time (&start);
	mergesort2(a,0,N-1);
	//mergesort(a,0,N-1);
	//sort(a,a+N);
	//stable_sort(a,a+N);
	time (&end);
	double dif = difftime (end,start);
	printf ("It took you %.2lf seconds to sort.\n", dif ); //It took you 31.00 seconds to sort.
	printarray(a,15200,15250);
	delete [] a;
	printf("memnum:%d\n",memnum);
}

void testmerge3(){
	//int aa[]={10,2};
	int aa[]={120,25,17,2,275};// inversionpair = 6
	cout << "inversion pair number:" << mergesort3(aa,0,sizeof(aa)/sizeof(int)-1) << endl;

 	const int N=static_cast<int>(20000);
	int* a=new int[N];
	for(int i=0;i<N;i++){a[i]=i;}
	random_shuffle(a,a+N);
	time_t start,end;
	time (&start);
	int inversionpair=mergesort3(a,0,N-1);
	//mergesort(a,0,N-1);
	//sort(a,a+N);
	//stable_sort(a,a+N);
	printf("inversion pair = %d\n", inversionpair);
	time (&end);
	double dif = difftime (end,start);
	printf ("It took you %.2lf seconds to sort.\n", dif ); //It took you 31.00 seconds to sort.
	printarray(a,15200,15250);
	delete [] a;
	printf("memnum:%d\n",memnum);
}


void test_sort(){
	/*int aa[]={2,8,7,1,3,5,6,4};
	simon::qksort(aa,0,sizeof(aa)/sizeof(int)-1);
	simon::test1();*/
	
	//insertionsort(aa);
	//mergesort(a,0,sizeof(a)/sizeof(int));
	//int aa[]={0,2,17,24,25,42,45,52,58,62,71,79,82,95,96,98,6,21,26,31,33,35,44,49,61,64,74,78,87,89,92,99};
	//mergesort2(aa,0,sizeof(aa)/sizeof(int)-1);
	//int a[]={4, 2, 9, 3 ,8, 6, 11};

	////testmerge1();
	////testmerge1();
	testmerge3();
	return;
}
